Self crossing

Time: O(N); Space: O(1); hard

You are given an array x of n positive numbers.

You: * start at point (0,0) and * moves x[0] metres to the North, then * x[1] metres to the West, * x[2] metres to the South, * x[3] metres to the East and so on.

In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

Self crossing

+---+
|   |
+---+----->
    |

Input: x = [2, 1, 1, 2],

Output: True

Example 2:

Not self crossing

+------+
|      |
|
|
+------------->

Input: x = [1, 2, 3, 4]

Output: Fallse

Example 3:

Self crossing

+------+
|      |
+------+---->

Input: x = [1, 1, 1, 1]

Output: True

class Solution1(object):
    def isSelfCrossing(self, x) -> bool:
        """
        :type x: List[int]
        :rtype: bool
        """
        if len(x) >= 5 and \
           x[3] == x[1] and \
           x[4] + x[0] >= x[2]:
            # Crossing in a loop
            return True

        for i in range(3, len(x)):
            if x[i] >= x[i - 2] and \
               x[i - 3] >= x[i - 1]:
                # Case 2: current line crosses the line 4 steps ahead of it
                #         Fourth line crosses first line and onward
                return True
            elif i >= 5 and x[i - 4] <= x[i - 2] and \
                            x[i] + x[i - 4] >= x[i - 2] and \
                            x[i - 1] <= x[i - 3] and \
                            x[i - 5] + x[i - 1] >= x[i - 3]:
                # Case 3: current line crosses the line 6 steps ahead of it
                #         Sixth line crosses first line and onward
                return True
        return False

s = Solution1()
x = [2, 1, 1, 2]
assert s.isSelfCrossing(x) == True
x = [1, 2, 3, 4]
assert s.isSelfCrossing(x) == False
x = [1, 1, 1, 1]
assert s.isSelfCrossing(x) == True

See also:

https://leetcode.com/problems/self-crossing

https://www.lintcode.com/problem/self-crossing